import java.util.Random;
import java.util.Scanner;

public class a {
    public static int[][] matrixchainorder(int[] p){
        int[][] k=new int[7][7];
        int[][] s=new int[7][7];
        for(int i=1;i<=6;i++){
            k[i][i]=0;
        }
        for(int i=6;i>=1;i--){
            for(int j=i+1;j<=6;j++){
                k[i][j]=Integer.MAX_VALUE;
                for(int m=i;m<j;m++){
                    int temp=k[i][m]+k[m+1][j]+p[i-1]*p[m]*p[j];
                    if(temp<k[i][j]){
                        k[i][j]=temp;
                        s[i][j]=m;
                    }
                }
            }
        }
        System.out.println("最小标量乘法次数:"+k[1][6]);
        return s;
    }
    public static String build(int[][] s,int i,int j){
        if(i==j){
            return "A"+i;
        }
        else{
            int k=s[i][j];
            String left=build(s,i,k);
            String right=build(s,k+1,j);
            return "("+left+right+")";
        }
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int s=scanner.nextInt();
        Random rand=new Random(s);
        int[] p=new int[7];
        for(int i=0;i<p.length;i++){
            p[i]=rand.nextInt(20)+1;
        }
        System.out.println("随机生成的矩阵的行和列");
        for(int i=0;i<p.length;i++) {
            System.out.println(p[i]);

        }
        int[][] l=matrixchainorder(p);
        String op=build(l,1,6);
        System.out.println("最优解法为"+op);


    }
}
